package list_;

import java.util.LinkedList;

public class LinkedList_ {

    public static void main(String[] args) {
        /**
         * 实现了双向链表和双端队列
         * 元素可以是重复的，可以为null
         * 线程不安全的
         */
        /**
         * 1.调用无参构造器，啥也没干
         * //todo
         *      public LinkedList() {}
         *      此时size=0 first=last=null
         *2.add
         * //todo
         *      public boolean add(E e) {
         *         linkLast(e);
         *         return true;
         *     }
         *3.执行linkLast(e)方法
         * //todo
         *      void linkLast(E e) {
         *         final Node<E> l = last;
         *         final Node<E> newNode = new Node<>(l, e, null);
         *         last = newNode;
         *         if (l == null)
         *             first = newNode;
         *         else
         *             l.next = newNode;
         *         size++;
         *         modCount++;
         *     }
         *    分析此时last\first\newNode都指向为e的节点
         *    将新节点加在链表最后
         *    1.先取出链表的尾节点，用临时变量l存放last
         *    2.创建一个新的节点
         *          前指针指向l
         *          后指针为空
         *    3.更新尾节点last为新加进来的节点，因为链表是尾插
         *    4.如果是第一次添加节点，那么l=last=null
         *          所以首节点也指向newNode
         *      否则存放原来尾节点的临时变量l的后指针指向newNode
         *      从而构成双向链表
         */
        LinkedList list=new LinkedList();
        list.add("liXu");

        //再多加几个元素
        list.add(16);
        list.add("帅哥");


        /**
         * 删除节点remove()
         *
         *
         */
        list.remove();//默认删除第一个
        /**
         * 1.调用的是removeFirst()
         * //todo
         *      public E remove() {
         *         return removeFirst();
         *     }
         * 2.调用removeFirst()
         * //todo
         *      public E removeFirst() {
         *         final Node<E> f = first;
         *         if (f == null)
         *             throw new NoSuchElementException();
         *         return unlinkFirst(f);
         *     }
         *     分析：取出头节点不为空才删除
         * 3.unlinkFirst(f)真正干活了
         * //todo
         *      private E unlinkFirst(Node<E> f) {
         *         // assert f == first && f != null;
         *         final E element = f.item;
         *         final Node<E> next = f.next;
         *         f.item = null;
         *         f.next = null; // help GC
         *         first = next;
         *         if (next == null)
         *             last = null;
         *         else
         *             next.prev = null;
         *         size--;
         *         modCount++;
         *         return element;
         *     }
         *
         */

        /**
         * 修改某个节点对象
         *
         */
        list.set(0,"黎旭");
        /**
         * 1.调用set()
         * //todo
         *      public E set(int index, E element) {
         *         checkElementIndex(index);//检查下标是否合法
         *         Node<E> x = node(index);//找到下标对应的节点，看源码可知index>=size/2会从尾节点开始找
         *         E oldVal = x.item;
         *         x.item = element;
         *         return oldVal;
         *     }
         * 2.
         *    分析首先检查下标 下标应当小于0且小于size
         *    //todo
         *          private void checkElementIndex(int index) {
         *         if (!isElementIndex(index))
         *             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
         *         }
         *     //todo
         *          private boolean isElementIndex(int index) {
         *         return index >= 0 && index < size;
         *          }
         * 3.根据下标找到节点
         * //todo
         *      Node<E> node(int index) {
         *         // assert isElementIndex(index);
         *         if (index < (size >> 1)) {  //index<size/2会从头节点开始找
         *             Node<E> x = first;
         *             for (int i = 0; i < index; i++)
         *                 x = x.next;
         *             return x;
         *         } else {  //index>=size/2会从尾节点开始找
         *             Node<E> x = last;
         *             for (int i = size - 1; i > index; i--)
         *                 x = x.prev;
         *             return x;
         *         }
         *     }
         * 4.找到后更新此节点的val值
         * 5.并将旧值返回
         *
         */

        /**
         * 获取某一个节点
         */
        list.get(0);
        /**
         * 同样先检测下标是否合法在调用根据下标查找节点
         * 返回值是节点的值
         * //todo
         *      public E get(int index) {
         *         checkElementIndex(index);
         *         return node(index).item;
         *     }
         */
    }

}
